package com.gali.leetcode.day3;

/**
 * @Auther: gali
 * @Date: 2022/7/16-07-16-21:25
 * @Description:最长回文子串
 */
public class Solution1 {
    //动态规划求解。
    public String longestPalindrome(String s) {
        //定义一个表示字符长度
        int len = s.length();
        //如果字符小于2，直接返回
        if(len < 2){
            return s;
        }
        //定义一个表示回文字符数量的变量
        int maxlen = 1;
        //回文字串的开始索引
        int begin = 0;
        //定义一个存储所有可能的结果，一个二维数组
        boolean[][] dp = new boolean[len][len];
        //单个字符本身就是回文串
        for(int i = 0; i< len; i++){
            dp[i][i] = true;
        }
        //递归遍历，二维数组的对角线上方的所有元素
        for(int j =1; j<len;j++){
            for(int i =0; i<len-1 && i<j;i++){
                //如果两个字符相等，就说明不是回文串
                if(s.charAt(i) != s.charAt(j)){
                    dp[i][j] = false;
                }else{
                    //当是回文串时，字符个数小于等于3个，就是回文串
                    if(j-i<3){
                        dp[i][j] =  true;
                    }else{
                        //递归判断当边界两边的字符相等时，继续判断内层的字符是否相等
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                //对比所有的回文串，取出长度最大的，回文串的起始位置
                if(dp[i][j] && j-i+1 > maxlen){
                    maxlen = j-i+1;
                    begin = i;
                }
            }
        }
        //字符串的切割
        return s.substring(begin,begin+maxlen);
    }
}
